A database join operation combines records from more than one database table. A join essentially creates a set that can be saved as its own independent database table. There are a variety of types of joins.
One type of join is called inner join. An inner join creates a common results table from two tables by combining common values from the two tables via a join predicate. Another type is outer join. An outer join does not require each record in the two joined tables to have a corresponding matching record. The resulting joined table retains each record, even if no other matching record exists. Outer joins may be subdivide further into left outer joins, right outer joins, and full outer joins, depending on which table(s) the rows are retained from, such as left, right, or both. A left outer join retains all records from the left table regardless of matching and retains only matching records from a right table. Conversely, a right outer join retains all records from a right table regardless of matching and retains only matching records from the left table. A full outer join includes records from both the left and right tables regardless of matching.
Traditionally, databases have been partitioned based on rows (sometimes referred to as “horizontal partitioning”). However, recently databases have permitted partitioning based on columns (also referred to as “vertical partitioning”).
Vertical partitioning for database tables and join indexes is a powerful physical database design choice that has only recently been made available in the industry. A key advantage of column partitioning is to reduce the Input/Output (I/O) cost of accessing the underlying database objects by eliminating unnecessary access to columns that are not referenced in a given query in the projection list, join conditions, and/or elsewhere.
Since the cost of a join operation over column partitioned (“column partition” is herein referred to as “CP”) objects is usually a dominate factor in the overall cost of answering a given join query, optimizing join processing over CP objects is crucial to the query performance.
Join processing on a column-partitioned table for a parallel system can be done by duplicating or redistributing the other table on every Access Module Processor (AMP); by duplicating; or redistributing the column-partitioned table across all the AMPs. If the other table is duplicated, the column-partitioned table can be directly accessed in the join operation, in which case, the join columns in the column-partitioned table are accessed first to evaluate the join conditions. The remaining columns are accessed only for rows that satisfy the join conditions. Therefore for a join that qualifies a relatively small number of rows, duplicating the other table to directly join with the column-partitioned table can also achieve good Input/Output (I/O) reduction. However, when the other table is too large to be duplicated, the column-partitioned table will need to be duplicated or redistributed into a spool file to do the join. Conventionally, any time it is necessary to spool a column-partitioned table for a join operation, all the columns that are referenced by a given query are read and output to a spool file. This incurs un-necessary I/O in reading the non-join columns for rows that are not going to qualify for the join conditions, which is inefficient.
Moreover, large scale databases include query optimizers (may also be referred to as “database optimizers”) that determine a most efficient way to execute a query by considering multiple different query plans and the cost of each individual query plan. However, because conventional row-based database systems generally process joins with the assumption that there is very little overhead to access columns with a row once a row has been read, column-level options are not used by query optimizers in making query plan decisions for joins on CP tables.